/*
 
MS interview
Let A and B be two sequence of n integers each. Given an integer m, describe an O(nlogn) time algorithm for determining if there is an integer a in A and b in B such that m=a+b. 

*/

#include "junix.h"

bool f(int a[],int asz, int b[], int bsz, int m) {
	typedef std::vector<std::vector<int> > hashtable;
	hashtable ha(m,std::vector<int>());
	hashtable hb(m,std::vector<int>());

	for (int i=0;i<asz;i++) 
		ha[a[i]%m].push_back(a[i]);

	for (int i=0;i<bsz;i++) 
		hb[b[i]%m].push_back(b[i]);

	for (int i=0;i<m;i++)
   	{
		std::sort(ha[i].begin(),ha[i].end());
		std::sort(hb[i].begin(),hb[i].end());
	}

	for (int i=0;i<m;i++) 
	{
		int bindex=(m-i)%m;
		typedef std::vector<int>::iterator iterator;
		iterator apos = ha[i].begin();
		iterator bpos = hb[bindex].end()-1;

		while (apos!=ha[i].end() && bpos >= hb[bindex].begin() )
	   	{
			int ret = *apos+*bpos;
			if (ret==m) {
				printf("a=%d,b=%d\n",*apos, *bpos);
			} else if (ret<m) {
				++apos;
			} else 	{
				++bpos;
			}
		}
	}

	return false;
}	

int main(){
	int a[]={1,2,3,4,5};
	int b[]={3,4,5,6,7};
	f(a,5,b,5,12);
}
